#pragma once

#include <algorithm>
#include <memory>

#include "ezstl_allocator.hpp"
#include "ezstl_construct.hpp"
#include "ezstl_iterator_base.hpp"
#include "ezstl_uninitialized.hpp"

namespace ezstl {

/*
+----+----+
|    |    |
+----+----+
^
map
*/

#define BufSize 512

template <typename T, typename Ref, typename Ptr>
struct DequeIterator {
  using iterator_category = random_access_iterator_tag;
  using value_type = T;
  using difference_type = std::ptrdiff_t;
  using pointer = Ptr;
  using reference = Ref;

  using size_type = std::size_t;
  using iterator = DequeIterator<T, T &, T *>;
  using const_iterator = DequeIterator<T, const T &, const T *>;
  using map_pointer = T **;

  value_type *cur;    // 当前迭代器在缓冲区的行位置
  value_type *first;  // 缓冲区头
  value_type *last;   // 缓冲区的尾部（和含备用空间）
  map_pointer node;   // 指向map中迭代器所在的节点

  static inline size_type buffer_size() {
    return BufSize != 0 ? BufSize
                        : (sizeof(value_type) < 512 ? 512 / sizeof(value_type)
                                                    : size_type(1));
  }
  DequeIterator()
      : cur(nullptr), first(nullptr), last(nullptr), node(nullptr) {}
  DequeIterator(T *p, map_pointer mp)
      : cur(p), first(*mp), last(*mp + buffer_size()), node(mp) {}
  DequeIterator(const iterator &other)
      : cur(other.cur),
        first(other.first),
        last(other.last),
        node(other.node) {}
  // DequeIterator &operator=(const iterator &other) {
  //   // set_node(other.node);
  //   cur = other.cur;
  // }

  // 跳到下一个缓冲区
  void set_node(map_pointer new_node) {
    node = new_node;
    first = *node;
    last = first + difference_type(buffer_size());
  }

  reference operator*() const { return *cur; }
  pointer operator->() const { return cur; }
  difference_type operator-(const iterator &oi) const {
    return difference_type(buffer_size()) * (node - oi.node - 1) +
           (cur - first) + (oi.last - oi.cur);
  }

  DequeIterator &operator++() {
    ++cur;
    if (cur == last) {
      set_node(node + 1);
      cur = first;
    }
    return *this;
  }

  DequeIterator operator++(int) {
    DequeIterator tmp = *this;
    ++(*this);
    return tmp;
  }

  DequeIterator &operator--() {
    if (cur == first) {
      set_node(node - 1);
      cur = last;
    }
    --cur;
    return *this;
  }

  DequeIterator operator--(int) {
    DequeIterator tmp = *this;
    --(*this);
    return tmp;
  }

  DequeIterator &operator+=(difference_type n) {
    difference_type offset = n + (cur - first);
    if (offset > 0 && offset < difference_type(buffer_size())) {
      // target 在同一缓冲区
      cur += n;
    } else {
      difference_type node_offset =
          offset > 0 ? offset / difference_type(buffer_size())
                     // TODO: ??? 负数向下取整
                     : -difference_type((-offset - 1) / buffer_size()) - 1;
      set_node(node + node_offset);
      cur = first + (offset - node_offset * difference_type(buffer_size()));
    }
    return *this;
  }

  DequeIterator operator+(difference_type n) {
    DequeIterator tmp = *this;
    return tmp += n;
  }

  DequeIterator &operator-=(difference_type n) { return *this += (-n); }

  DequeIterator operator-(difference_type n) {
    DequeIterator tmp = *this;
    return tmp -= n;
  }

  reference operator[](difference_type n) const { return *(*this + n); }

  bool operator==(const DequeIterator &other) const { return cur == other.cur; }
  bool operator!=(const DequeIterator &other) const {
    return !(*this == other);
  }
  bool operator<(const DequeIterator &other) const {
    return (node == other.node) ? (cur < other.cur) : (node < other.node);
  }
};

template <typename T, typename Alloc = Allocator<T>>
class Deque {
 public:
  using value_type = T;
  using allocator_type = Alloc;
  using size_type = std::size_t;
  using difference_type = std::ptrdiff_t;
  using reference = value_type &;
  using const_reference = const value_type &;
  using pointer = value_type *;
  using const_pointer = const value_type *;

  using iterator = DequeIterator<value_type, reference, pointer>;
  using const_iterator =
      DequeIterator<value_type, const_reference, const_pointer>;

 protected:
  // pointer of pointer of T
  using map_pointer = pointer *;
  iterator start;   // 表现第一个节点
  iterator finish;  // 表现最后一个节点
  map_pointer
      map;  // 指向map，map是块连续的空间，每个元素都是指针，指向一个缓冲区
  size_type map_size;
  using map_alloc = Allocator<pointer>;
  using data_alloc = Alloc;

 public:
  void show() {
    for (auto i = begin(); i != end(); ++i) {
      std::cout << *i << " ";
    }
    std::cout << "size: " << size() << std::endl;
  }

 public:
  Deque(size_type n, const_reference value)
      : start(), finish(), map(nullptr), map_size(0) {
    initialize_map(n);
    fill_initialize(n, value);
  }
  Deque() : start(), finish(), map(nullptr), map_size(0) { initialize_map(0); }
  template <typename InputIterator>
  Deque(InputIterator first, InputIterator last)
      : start(), finish(), map(nullptr), map_size(0) {
    initialize_map(0);
    insert(begin(), first, last);
  }

  ~Deque() {
    ezstl::destroy(start, finish);
    destroy_nodes(start.node, finish.node + 1);
    map_alloc::deallocate(map, map_size);
  }

  // Element access
  reference operator[](size_type n) { return start[difference_type(n)]; }
  const_reference operator[](size_type n) const {
    return start[difference_type(n)];
  }
  reference at(size_type pos) { return operator[](pos); }
  const_reference at(size_type pos) const { return operator[](pos); }
  reference front() { return *start; }
  const_reference front() const { return *start; }
  reference back() {
    iterator tmp = finish;
    --tmp;
    return *tmp;
  }
  const_reference back() const {
    iterator tmp = finish;
    --tmp;
    return *tmp;
  }

  // Iterators
  iterator begin() { return start; }
  const_iterator begin() const { return start; }
  const_iterator cbegin() const { return start; }
  iterator end() { return finish; }
  const_iterator end() const { return finish; }
  const_iterator cend() const { return finish; }

  // Capacity
  bool empty() const { return start == finish; }
  size_type size() const { return finish - start; }
  size_type max_size() const { return size_type(-1); }

  // Modifiers
  void clear() {
    for (map_pointer node = start.node + 1; node < finish.node; ++node) {
      ezstl::destroy(*node, *node + iterator::buffer_size());
      data_alloc::deallocate(*node, iterator::buffer_size());
    }

    if (start.node != finish.node) {  // start 与 finish 缓冲区 分别为2个
      ezstl::destroy(start.cur, start.last);
      ezstl::destroy(finish.first, finish.first);
      // 释放finish 缓冲区，保留 start 缓冲区
      data_alloc::deallocate(finish.first, iterator::buffer_size());
    } else {
      // 保留 start 缓冲区
      ezstl::destroy(start.cur, start.last);
    }
    finish = start;
  }
  iterator insert(const_iterator pos, const_reference value) {
    if (pos.cur == start.cur) {
      push_front(value);
      return start;
    }
    if (pos.cur == finish.cur) {
      push_back(value);
      iterator tmp = finish;
      --tmp;
      return tmp;
    }
    return insert_aux(pos.iterator_const_cast(), value);
  }
  // iterator insert(const_iterator pos, value_type &&value);  // TODO: lvalue
  iterator insert(const_iterator pos, size_type count, const_reference value) {
    difference_type offset = pos - start;
    if (count == 0) return start + offset;
    if (pos.cur == start.cur) {
      iterator new_start = reserve_elements_at_front(count);
#if 0
      for (map_pointer cur = new_start.node; cur < start.node; ++cur)
        ezstl::uninitialized_fill(*cur, *cur + iterator::buffer_size(), value);
      ezstl::uninitialized_fill(new_start.cur, new_start.last, value);
      start = new_start;
#else
      try {
        ezstl::uninitialized_fill(new_start, start, value);
        start = new_start;
      } catch (...) {
        destroy_nodes(new_start.node, start.node);
        throw;
      }
#endif
    } else if (pos.cur == finish.cur) {
      iterator new_finish = reserve_elements_at_back(count);
      try {
        ezstl::uninitialized_fill(finish, new_finish, value);
        finish = new_finish;
      } catch (...) {
        destroy_nodes(finish.node + 1, new_finish.node + 1);
        throw;
      }
    } else {
      insert_count_aux(iterator{pos.cur, pos.node}, count, value);
    }
    return start + offset;
  }
  template <typename InputIt>
  iterator insert(const_iterator pos, InputIt first, InputIt last) {
    difference_type offset = pos - start;
    if (first == last) return start + offset;
    size_type count = ezstl::distance(first, last);
    if (pos.cur == start.cur) {
      iterator new_start = reserve_elements_at_front(count);
      try {
        ezstl::uninitialized_copy(first, last, new_start);
        start = new_start;
      } catch (...) {
        destroy_nodes(new_start.node, start.node);
        throw;
      }
    } else if (pos.cur == finish.cur) {
      iterator new_finish = reserve_elements_at_back(count);
      try {
        ezstl::uninitialized_copy(first, last, finish);
        finish = new_finish;
      } catch (...) {
        destroy_nodes(finish.node + 1, new_finish.node + 1);
        throw;
      }
    } else {
      insert_range_aux(iterator{pos.cur, pos.node}, first, last);
    }
    return start + difference_type(offset);
  }

  iterator erase(iterator pos) {
    auto next = pos;
    ++next;
    difference_type index = pos - start;
    if (index < (size() >> 1)) {  // pos 之前的元素个数较少
      // TODO: ezstl::copy or move_backward
      std::copy_backward(start, pos, next);  // 将前面的元素向后拷贝
      pop_front();                           // 使用 copy 需要pop第一个元素
    } else {
      // TODO: ezstl::copy
      std::copy(next, finish, pos);
      pop_back();
    }
    return start + index;
  }
  iterator erase(iterator first, iterator last) {
    if (first == start && last == finish) {
      clear();
      return finish;
    }
    difference_type n = last - first;              // 计算剩余需要删除的个数
    difference_type elems_before = first - start;  // 区间前方的元素个数
    if (elems_before < ((size() - n) >> 1)) {
      // TODO: ezstl::copy or (move_backward)
      iterator new_start = std::copy_backward(start, first, last);
      // 析构多余元素 （原因使用copy）
      ezstl::destroy(start, new_start);
      // 释放多余缓冲区
      for (map_pointer cur = start.node; cur < new_start.node; ++cur)
        data_alloc::deallocate(*cur, iterator::buffer_size());
      start = new_start;
    } else {
      // TODO: ezstl::copy or (move)
      iterator new_finish = std::copy(last, finish, first);
      ezstl::destroy(finish, new_finish);
      for (map_pointer cur = new_finish.node + 1; cur < finish.node; ++cur)
        data_alloc::deallocate(*cur, iterator::buffer_size());
      finish = new_finish;
    }
    return start + elems_before;
  }

  void push_back(const_reference value) {
    if (finish.cur != finish.last - 1) {
      ezstl::construct(finish.cur, value);
      ++finish.cur;
    } else {  // 最后一个缓冲区只剩最后一个元素空位
      push_back_aux(value);
    }
  }

  void pop_back() {
    if (finish.cur != finish.first) {
      // 弹出后当前缓冲区还有一个或更多元素
      --finish.cur;
      ezstl::destroy(finish.cur);
    } else {  // 此时finish缓冲区中没有元素
      pop_back_aux();
    }
  }

  void push_front(const_reference value) {
    if (start.cur != start.first) {
      ezstl::construct(start.cur - 1, value);
      --start.cur;
    } else {  // 开始缓冲区中没有空位
      push_front_aux(value);
    }
  }

  void pop_front() {
    if (start.cur != start.last - 1) {
      destroy(start.cur);
      ++start.cur;
    } else {  // 此时start缓冲区中只有一个元素
      pop_front_aux();
    }
  }

  void resize(size_type count, const_reference value) {
    if (count == size()) return;
    if (count < size()) {
      erase(start + count, finish);
    } else {
      insert(finish, finish + count - size(), value);
    }
  }

  void resize(size_type count) { resize(count, value_type{}); }

 private:
  void fill_initialize(size_type n, const_reference value) {
    map_pointer cur = nullptr;
    try {
#if 0
      for (cur = start.node; cur < finish.node; ++cur)
        ezstl::uninitialized_fill(*cur, *cur + iterator::buffer_size(), value);
      ezstl::uninitialized_fill(finish.first, finish.cur, value);
#else
      ezstl::uninitialized_fill(start, finish, value);
#endif
    } catch (...) {
#if 0
      ezstl::destroy(start, iterator{*cur, cur});
#else
      destroy_nodes(start.node, finish.node + 1);
#endif
    }
  }

  void initialize_map(size_type num_elements) {
    // 需要节点数 = 元素数 / 缓冲区可容纳元素个数 + 1
    size_type num_nodes = num_elements / iterator::buffer_size() + 1;
    map_size = std::max(INITIAL_MAP_SIZE, num_nodes + 2);
    map = map_alloc::allocate(map_size);

    map_pointer new_start = map + (map_size - num_nodes) / 2;
    map_pointer new_finish = new_start + num_nodes;

    try {
      create_nodes(new_start, new_finish);
    } catch (...) {
      map_alloc::deallocate(new_start, map_size);
      map = nullptr;
      map_size = 0;
      throw;
    }

    start.set_node(new_start);
    finish.set_node(new_finish - 1);
    start.cur = start.first;
    finish.cur = finish.first + num_elements % iterator::buffer_size();
  }

  void create_nodes(map_pointer start, map_pointer finish) {
    map_pointer cur = nullptr;
    try {
      for (cur = start; cur < finish; ++cur) *cur = allocate_node();
    } catch (...) {
      destroy_nodes(start, cur);
      throw;
    }
  }

  void destroy_nodes(map_pointer start, map_pointer finish) {
    map_pointer cur = nullptr;
    for (cur = start; cur < finish; ++cur) deallocate_node(*cur);
  }

  pointer allocate_node() {
    // return Allocator<value_type>::allocate(iterator::buffer_size());
    return Alloc::allocate(iterator::buffer_size());
  }
  void deallocate_node(value_type *p) {
    Alloc::deallocate(p, iterator::buffer_size());
  }

  iterator insert_aux(iterator pos, const_reference value) {
    difference_type index = pos - start;
    value_type copy_v = value;
    if (index < (size() >> 1)) {
      push_front(front());
      iterator front1 = start;
      ++front1;
      iterator front2 = front1;
      ++front2;
      pos = start + index;
      iterator pos1 = pos;
      ++pos1;
      std::copy(front2, pos1, front1);
    } else {
      push_back(back());
      iterator back1 = finish;
      --back1;
      iterator back2 = back1;
      --back2;
      pos = start + index;
      std::copy_backward(pos, back2, back1);
    }
    *pos = copy_v;
    return pos;
  }

  void insert_count_aux(iterator pos, size_type count, const_reference value) {
    size_type elems_before = pos - start;
    size_type len = size();
    if (elems_before < difference_type(len >> 1)) {
      iterator new_start = reserve_elements_at_front(count);
      try {
        if (elems_before >= count) {  // pos前方元素多与插入的元素个数
          // TODO: uninitialized_move
          // ezstl::uninitialized_copy(start, start + difference_type(count),
          //                           new_start);
          // TODO: ezstl::uninitialized_move
          // 将开头count个元素从原位置 移动 到
          // 新位置(没有构造过对象只有内存空间) 调用移动构造函数
          std::uninitialized_move(start, start + difference_type(count),
                                  new_start);
          // 将pos前方剩下的元素使用 move 调用移动拷贝函数到新位置，
          std::move(start + difference_type(count), pos, start);
          // 填充新元素
          std::fill(pos - difference_type(count), pos, value);
          start = new_start;
        } else {  // count > elems_before
          // 将pos前方所有元素调用移动构造函数 移动到new_start处
          std::uninitialized_move(start, pos, new_start);
          // 填充存在对象的位置，拷贝赋值函数
          std::fill(start, pos, value);
          // 未初始化空间使用placement new
          ezstl::uninitialized_fill(new_start + elems_before, start, value);
          start = new_start;
        }
      } catch (...) {
        destroy_nodes(new_start.node, start.node);
        throw;
      }
    } else {
      iterator new_finish = reserve_elements_at_back(count);
      size_type elems_after = len - elems_before;
      try {
        if (elems_after >= count) {
          std::uninitialized_move(finish - count, finish, finish);
          std::move_backward(pos, finish - count, finish);
          std::fill(pos, pos + count, value);
          finish = new_finish;
        } else {
          std::uninitialized_move(pos, finish, pos + count);
          std::fill(pos, finish, value);
          ezstl::uninitialized_fill(finish, pos + count, value);
          finish = new_finish;
        }
      } catch (...) {
        destroy_nodes(finish.node + 1, new_finish.node + 1);
      }
    }
  }

  template <typename InputIterator>
  void insert_range_aux(iterator pos, InputIterator first, InputIterator last) {
    size_type elems_before = pos - start;
    size_type count = ezstl::distance(first, last);
    size_type len = size();
    if (elems_before < difference_type(len >> 1)) {
      iterator new_start = reserve_elements_at_front(count);
      try {
        if (elems_before >= count) {
          std::uninitialized_move(start, start + difference_type(count),
                                  new_start);
          std::move(start + difference_type(count), pos, start);
          std::copy(first, last, pos - difference_type(count));
        } else {
          iterator tmp = std::uninitialized_move(start, pos, new_start);
          tmp = std::uninitialized_copy(first, first + (count - elems_before),
                                        tmp);
          std::copy(first + (count - elems_before), last, tmp);
        }
      } catch (...) {
        ezstl::destroy(new_start.node, start.node);
        throw;
      }
    } else {
      iterator new_finish = reserve_elements_at_back(count);
      size_type elems_after = finish - pos;
      try {
        if (elems_after >= count) {
          std::uninitialized_move(pos, finish, pos + count);
          std::move_backward(pos, finish - count, finish);
          std::copy(first, last, pos);
          finish = new_finish;
        } else {
          std::uninitialized_move(pos, finish, pos + count);
          std::copy(first, first + elems_after, pos);
          std::uninitialized_copy(first + elems_after, last, finish);
          finish = new_finish;
        }
      } catch (...) {
        destroy_nodes(finish.node + 1, new_finish.node + 1);
        throw;
      }
    }
  }

  // Called only finish.cur == finish.last - 1
  void push_back_aux(const_reference value) {
    value_type copy_v = value;
    reserve_map_at_back();                 // 若符合某种条件必须重换一个map
    *(finish.node + 1) = allocate_node();  // 配置一个新节点（缓冲区）
    try {
      ezstl::construct(finish.cur,
                       copy_v);  // 在最后一个缓冲区的最后一个空位放入元素
      finish.set_node(finish.node + 1);  // 修改finish，令其指向新缓冲区
      finish.cur = finish.first;
    } catch (...) {
      deallocate_node(*(finish.node + 1));
      throw;
    }
  }

  // Called only start.cur == start.first
  void push_front_aux(const_reference value) {
    value_type copy_v = value;
    reserve_map_at_front();               // 判断是否需要扩容map
    *(start.node - 1) = allocate_node();  // 分配一个新缓冲区
    try {
      start.set_node(start.node - 1);
      start.cur = start.last - 1;
      ezstl::construct(start.cur, copy_v);
    } catch (...) {
      // commit or rollback
      start.set_node(start.node + 1);
      start.cur = start.first;
      deallocate_node(*(start.node - 1));
      throw;
    }
  }

  // Called only finish.cur == finish.first
  void pop_back_aux() {
    deallocate_node(finish.first);
    finish.set_node(finish.node - 1);
    finish.cur = finish.last - 1;
    destroy(finish.cur);
  }

  // Called only start.cur == start.last - 1
  void pop_front_aux() {
    ezstl::destroy(start.cur);
    deallocate_node(start.first);
    start.set_node(start.node - 1);
    start.cur = start.first;
  }

  // 向map尾部提添加节点，如果需要扩容进行扩容
  void reserve_map_at_back(size_type nodes_to_add = 1) {
    if (nodes_to_add > map_size - (finish.node + 1 - map))
      // 如果map尾部剩下的node数不足以添加新node
      reallocate_map(nodes_to_add, false);
  }
  void reserve_map_at_front(size_type nodes_to_add = 1) {
    if (nodes_to_add > start.node - map) reallocate_map(nodes_to_add, true);
  }

  iterator reserve_elements_at_front(size_type elems) {
    size_type vacancies = start.cur - start.first;
    if (elems > vacancies) new_elemnts_at_front(elems - vacancies);
    return start - difference_type(elems);
  }

  iterator reserve_elements_at_back(size_type elems) {
    size_type vacancies = finish.last - finish.cur - 1;
    if (elems > vacancies) new_elements_at_back(elems - vacancies);
    return finish + difference_type(elems);
  }

  void new_elemnts_at_front(size_type elems) {
    // 向上取整
    size_type new_nodes =
        (elems + iterator::buffer_size() - 1) / iterator::buffer_size();
    reserve_map_at_front(new_nodes);
    size_type i = 0;
    try {
      for (i = 1; i <= new_nodes; ++i) *(start.node - i) = allocate_node();
    } catch (...) {
      for (size_type j = 1; j < i; ++j) deallocate_node(*(start.node - i));
      throw;
    }
  }

  void new_elements_at_back(size_type elems) {
    size_type new_nodes =
        (elems + iterator::buffer_size() - 1) / iterator::buffer_size();
    reserve_map_at_back(new_nodes);
    size_type i = 0;
    try {
      for (i = 1; i <= new_nodes; ++i) *(finish.node + i) = allocate_node();
    } catch (...) {
      for (size_type j = 1; j < i; ++j) deallocate_node(*(finish.node + j));
      throw;
    }
  }

  void reallocate_map(size_type node_to_add, bool to_add_front) {
    size_type old_num_nodes = finish.node - start.node + 1;
    size_type new_num_nodes = old_num_nodes + node_to_add;

    map_pointer new_start = nullptr;
    if (map_size > 2 * new_num_nodes) {  // 容量够
      // TODO: ??? offset = (mpa_size - new_num_nodes) / 2 + node_to_add
      // (map_size - new_num_nodes) / 2 平分剩余元素
      new_start = map + (map_size - new_num_nodes) / 2 +
                  (to_add_front ? node_to_add : 0);
      if (new_start < start.node)
        // TODO: ezstl::copy or (copy and move)
        // std::copy(start.node, finish.node + 1, new_start);
        std::move(start.node, finish.node + 1, new_start);
      else
        // TODO:: ezstl::copy or (copy_backward and move_backward)
        // std::copy_backward(start.node, finish.node, new_start +
        // old_num_nodes);
        std::move_backward(start.node, finish.node + 1,
                           new_start + old_num_nodes);
    } else {
      size_type new_map_size = map_size + std::max(map_size, node_to_add) + 2;
      map_pointer new_map = map_alloc::allocate(new_map_size);
      new_start = new_map + (new_map_size - new_num_nodes) / 2 +
                  (to_add_front ? node_to_add : 0);
      // TODO: ezstl::copy or move
      std::move(start.node, finish.node, new_map);
      map_alloc::deallocate(map, map_size);
      map = new_map;
      map_size = new_map_size;
    }
    start.set_node(new_start);
    // TODO: ???
    finish.set_node(new_start + old_num_nodes - 1);
  }

 private:
  const size_type INITIAL_MAP_SIZE = 8;
};

}  // namespace ezstl